2 BOOLEAN ALGEBRA

If X is a set, there is a (unique) set the elements of which are all subsets
of X; it written $(X). We have 0 e gJ(X), X e $(X); the relations * e X,
are equivalent; the relations Y c X, Y e ^S(X) are equivalent

PROBLEM

Show that the set of all subsets of a finite set having n elements (n ^ 0) is a finite set
having 2" elements.

2. BOOLEAN ALGEBRA

If X, Y are two sets such that Y c X, the set {x e X | x $ Y) is a subset
of X called the difference of X and Y or the complement of Y with respect
to X, and written X — Y or Qx Y (or (J Y when there is no possible confusion).

Given two sets X, Y, there is a set whose elements are those which belong
to both X and Y, namely {x e X | x e Y}; it is called the intersection of X and Y
and written X n Y. There is also a set whose elements are those which
belong to one at least of the two sets X, Y; it is called the union of X and Y
and written X u Y.

The following propositions follow at once from the definitions:

(1.2.1) X-X = 0, X-0-X.

(1.2.2) XuX = X9 XnX = X.

(1.2.3) XuY = YuX, XnY = YnX.

(1.2.4) The relations X c Y, X u Y = Y, X n Y = X are equivalent.

(1.2.5) XcXuY, XnYcX.

(1.2.6) The relation "X c Z and Y c Z" is equivalent to X u Y c Z;

the relation " Z c X and Z c Y " is equivalent to Z c X n Y.

(1.2.7) Xu(YuZ) = (Xu Y)uZ, written X u Y u Z.
X n (Y n Z) = (X n Y) n Z, written X n Y n Z.

(1.2.8) X u (Y n Z) = (X u Y) n (X u Z)

X n (Y u Z) = (X n Y) u (X n Z) (distributivity).